using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Storage;

namespace Evolution.Engine.Objects
{
    public class QuadtreeGameComponent : DrawableGameComponent
    {
        public QuadtreeGameComponent(Game game)
            : base(game)
        {
            _quadtree = null;
            qNode = null;
        }

        ///<summary>
        /// The derrived class can override this method or the method
        /// QuadtreeGameComponent.Draw(GameTime gameTime, Matrix view, Maxtrix projection)
        /// but should not (in most all cases) override both.
        /// Note that Draw will be called only when the object is visible in the Quadtree
        /// </summary>
        /// <param name="gameTime">The elapsed time since the last frame.</param>
        public override void Draw(GameTime gameTime)
        {
            base.Draw(gameTime);
        }

        ///<summary>
        /// The derrived class can override this or the DrawableGameComponent.Draw(GameTime gameTime)
        /// but should not (in most all cases) override both.
        /// Note that Draw will be called only when the object is visible in the Quadtree
        /// </summary>
        /// <param name="gameTime">The elapsed time since the last frame.</param>
        /// <param name="view">The current view matrix from the Quadtree.</param>
        /// <param name="projection">The current projection matrix from the Quadtree.</param>
        public virtual void Draw(GameTime gameTime, Matrix view, Matrix projection)
        {
            Draw(gameTime);
        }

        /// <summary>
        /// Gets or Sets the QuadtreeGameComponents position within the terrain
        /// Note: You must set the position all at once (ie, Position = vector
        ///       NOT Position.X = nnn, Position.Z = nnn, etc...)
        /// </summary>
        public Vector3 Position
        {
            get { return _position; }
            set
            {
                _position = value;
                if (qNode != null)
                {
                    if (qNode.IsInThisNode(Position))
                        return;
                    qNode.RemoveComponent(this);
                }
                if (_quadtree != null)
                    _quadtree.AddComponent(this);
            }
        }

        /// <summary>
        /// Gets the Quadtree that this QuadtreeGameComponent is attached to.
        /// </summary>
        public Quadtree Quadtree
        {
            get { return _quadtree; }
        }

        // Work around for protected access to some DrawableGameComponent methods
        // need to call these from Quadtree since it is the ComponentManager
        // of QuadtreeGameComponents.

        internal void X_LoadGraphicsContent(bool LoadAll)
        {
            LoadGraphicsContent(LoadAll);
        }
        internal void X_UnloadGraphicsContent(bool unloadAll)
        {
            UnloadGraphicsContent(unloadAll);
        }

        // member variables
        internal Quadtree _quadtree;
        internal QuadTreeNode qNode;
        internal Vector3 _position;
    }

    //=======================================
    //  QuadTreeModelInfo
    //=======================================

    public class QuadtreeModelInfo
    {
        internal QuadtreeModelInfo(Model m, Vector3 p, float s, Vector3 r)
        {
            model = m;
            position = p;
            rotation = r;
            scale = s;
            node = null;

            userObject = null;
        }
        public Vector3 Position
        {
            get { return position; }
        }
        public Model Model
        {
            get { return model; }
        }
        public float Scale
        {
            get { return scale; }
        }
        public Vector3 Rotation
        {
            get { return rotation; }
            set { rotation = value; }
        }
        internal Model model;
        internal Vector3 position;
        internal float scale;
        internal Vector3 rotation;
        internal QuadTreeNode node;
        public Object userObject;
    }

    //=======================================
    //  QuadTreeNode
    //=======================================

    class QuadTreeNode
    {
        const int NW = 0, NE = 1, SW = 2, SE = 3;

        public QuadTreeNode(QuadTreeNode parent)
        {
            m_parent = parent;

            child = new QuadTreeNode[4];

            // TryCull instance variables
            m_corners = new Vector3[8];
            m_projCorners = new Vector4[8];

            // Models and Components collections
            models = new Collection<QuadtreeModelInfo>();
            gameComponents = new Collection<QuadtreeGameComponent>();
        }

        //-------------------------------------------
        // Build the quadtree using the height data
        //-------------------------------------------

        public bool Buildout(GraphicsDevice gd, float cellSize, int sectorsize, int minX, int minY, int width, int height, float[,] heightData, Vector3[,] normals)
        {
            m_width = width;
            m_height = height;

            if (minX + m_width >= heightData.GetLength(1))
                m_width = heightData.GetLength(1) - minX - 1; // handle end of row case ( sectorsize - 1)
            if (minY + m_height >= heightData.GetLength(0))
                m_height = heightData.GetLength(0) - minY - 1; // handle end of column case (sectorsize - 1)

            m_cellSize = cellSize;

            // set instance variables that define world coords of this sector
            m_startX = cellSize * (float)minX;
            m_startY = cellSize * (float)minY;
            m_endX = cellSize * (float)(minX + m_width);
            m_endY = cellSize * (float)(minY + m_height);

            // now we don't need to do any more if we will delegate to children

            if (m_width > sectorsize || m_height > sectorsize)
            {
                int halfWidth = m_width / 2;
                if ((m_width & 0x01) == 0x01)
                    halfWidth++;
                int halfHeight = m_height / 2;
                if ((halfHeight & 0x01) == 0x01)
                    halfHeight++;

                m_minHeight = 999.0f;
                m_maxHeight = -999.0f;

                if (child[NW] == null)
                    child[NW] = new QuadTreeNode(this);
                child[NW].Buildout(gd, cellSize, sectorsize, minX, minY, halfWidth, halfHeight, heightData, normals);
                m_minHeight = child[NW].m_minHeight < m_minHeight ? child[NW].m_minHeight : m_minHeight;
                m_maxHeight = child[NW].m_maxHeight > m_maxHeight ? child[NW].m_maxHeight : m_maxHeight;

                if (width > sectorsize)
                {
                    if (child[NE] == null)
                        child[NE] = new QuadTreeNode(this);
                    child[NE].Buildout(gd, cellSize, sectorsize, minX + halfWidth, minY, halfWidth, halfHeight, heightData, normals);
                    m_minHeight = child[NE].m_minHeight < m_minHeight ? child[NE].m_minHeight : m_minHeight;
                    m_maxHeight = child[NE].m_maxHeight > m_maxHeight ? child[NE].m_maxHeight : m_maxHeight;
                }
                if (height > sectorsize)
                {
                    if (child[SW] == null)
                        child[SW] = new QuadTreeNode(this);
                    child[SW].Buildout(gd, cellSize, sectorsize, minX, minY + halfHeight, halfWidth, halfHeight, heightData, normals);
                    m_minHeight = child[SW].m_minHeight < m_minHeight ? child[SW].m_minHeight : m_minHeight;
                    m_maxHeight = child[SW].m_maxHeight > m_maxHeight ? child[SW].m_maxHeight : m_maxHeight;
                }

                if (height > sectorsize && width > sectorsize)
                {
                    if (child[SE] == null)
                        child[SE] = new QuadTreeNode(this);
                    child[SE].Buildout(gd, cellSize, sectorsize, minX + halfWidth, minY + halfHeight, halfWidth, halfHeight, heightData, normals);
                    m_minHeight = child[SE].m_minHeight < m_minHeight ? child[SE].m_minHeight : m_minHeight;
                    m_maxHeight = child[SE].m_maxHeight > m_maxHeight ? child[SE].m_maxHeight : m_maxHeight;
                }

                // find the 4 corners of this node (flat)
                // these are used in TryCull
                ComputeCorners();

                //----------------------------------------
                // we're done here!
                // We will only keep track of children nodes,
                // no data needed for rendering in this node
                //----------------------------------------
                return true;
            }

            //--------------------------------------
            // we are a lowest level child and have 
            // arrived at width and height <= sectorsize
            // save the height data for this sector
            // and create the data for rendering
            //--------------------------------------

            // we actually duplicate verts and heightdata on borders of sectors
            // that is, m_width and m_height are the number of cells
            // so the number of vertices is (m_width+1) * (m_height+1).
            // We save the heightdata in an instance variable so that we 
            // can compute GetHeightAt(x,y) later.

            m_heightData = new float[m_height + 1, m_width + 1];
            if (m_heightData == null)
                throw new Exception("QuadtreeNode.BuildOut : Out of memory for local heightData");

            m_minHeight = 9999.0f;
            m_maxHeight = -9999.0f;

            for (int y = 0; y <= m_height; y++)
            {
                for (int x = 0; x <= m_width; x++)
                {
                    m_heightData[y, x] = heightData[minY + y, minX + x];

                    float data = m_heightData[y, x];

                    if (data > m_maxHeight)
                        m_maxHeight = data;
                    if (data < m_minHeight)
                        m_minHeight = data;
                }
            }

            // find the 4 corners of this node (flat)
            // these are used in TryCull
            ComputeCorners();

            float totalHeight = (float)heightData.GetLength(0);
            float totalWidth = (float)heightData.GetLength(1);

            float ustep = 1.0f / totalWidth;// / (float )m_width;
            float ustart = (float)minX * ustep;
            float vstep = 1.0f / totalHeight;// / (float )m_height;
            float vstart = (float)minY * vstep;

            return CreateMeshFromHeightData(gd, minX, minY, ustart, ustep, vstart, vstep, normals);
        }


        //-------------------------------------------
        //  Create the Vertex Buffer and Index Buffer
        //  for this node
        //-------------------------------------------

        protected bool CreateMeshFromHeightData(GraphicsDevice gd, int minX, int minY, float ustart, float ustep, float vstart, float vstep, Vector3[,] normals)
        {
            // we duplicate vertices on sector borders (therefore, the +1)
            m_numVerts = (m_width + 1) * (m_height + 1);

            // Initialize the vertex buffer, allocating memory for each vertex

            m_vertexBuffer = new VertexBuffer(gd,
                VertexPositionNormalTexture.SizeInBytes * m_numVerts,
                ResourceUsage.None,
                ResourceManagementMode.Automatic);

            if (m_vertexBuffer == null)
                throw new Exception("QuadtreeNode.CreateMeshFromHeightData : Out of memory for VertexBuffer");

            // Create the vertices list

            VertexPositionNormalTexture[] vertList = new VertexPositionNormalTexture[m_numVerts];
            if (vertList == null)
                throw new Exception("QuadtreeNode.CreateMeshFromHeightData : Out of memory for vertList");

            int i = 0;
            for (int y = 0; y <= m_height; y++)
            {
                for (int x = 0; x <= m_width; x++)
                {
                    vertList[i].Position = new Vector3(m_startX + (x * m_cellSize), m_heightData[y, x], m_startY + (y * m_cellSize));
                    vertList[i].Normal = normals[minY + y, minX + x];
                    vertList[i].TextureCoordinate = new Vector2(ustart + (x * ustep), vstart + (y * vstep));
                    i++;
                }
            }

            // Set the vertex buffer data to the array of vertices

            m_vertexBuffer.SetData<VertexPositionNormalTexture>(vertList);

            // Create the indices that index into the vertex buffer

            m_numTris = m_width * m_height * 2; // 2 tri's per square (cell)
            short[] indices = new short[m_numTris * 3]; // 3 indices per tri

            if (indices == null)
                throw new Exception("QuadtreeNode.CreateMeshFromHeightData : Out of memory for indices");

            int vertsPerRow = m_width + 1;
            i = 0;
            for (int y = 0; y < m_height; y++)
            {
                int vertStart = y * vertsPerRow; // set to first vertice used in this row of indices

                for (int x = 0; x < m_width; x++)
                {
                    // cells upper left tri

                    indices[i++] = (short)(vertStart + vertsPerRow);
                    indices[i++] = (short)vertStart;
                    indices[i++] = (short)(vertStart + 1);

                    // cells lower right tri
                    indices[i++] = (short)(vertStart + vertsPerRow);
                    indices[i++] = (short)(vertStart + 1);
                    indices[i++] = (short)(vertStart + vertsPerRow + 1);

                    vertStart++; // set to next column of verts
                }
            }

            // create an index buffer with our indices

            m_indexBuffer = new IndexBuffer(
                gd,
                sizeof(short) * indices.Length,
                ResourceUsage.None,
                ResourceManagementMode.Automatic,
                IndexElementSize.SixteenBits
                );

            if (m_indexBuffer == null)
                throw new Exception("QuadtreeNode.CreateMeshFromHeightData : Out of memory for IndexBuffer");

            m_indexBuffer.SetData<short>(indices);

            return true;
        }

        void ComputeCorners()
        {
            m_corners[0].X = m_corners[1].X = m_startX;
            m_corners[2].X = m_corners[3].X = m_endX;
            m_corners[0].Z = m_corners[3].Z = m_startY;
            m_corners[1].Z = m_corners[2].Z = m_endY;
            m_corners[0].Y = m_corners[1].Y = m_corners[2].Y = m_corners[3].Y = m_minHeight;

            m_corners[4].X = m_corners[5].X = m_startX;
            m_corners[6].X = m_corners[7].X = m_endX;
            m_corners[4].Z = m_corners[7].Z = m_startY;
            m_corners[5].Z = m_corners[6].Z = m_endY;
            m_corners[4].Y = m_corners[5].Y = m_corners[6].Y = m_corners[7].Y = m_maxHeight;
        }

        //-------------------------------------------
        //  Attempt to cull this node out
        //  returns -1 = partially in viewing frustum
        //           0 = not in viewing frustum
        //           1 = totally in viewing frustum
        //-------------------------------------------

        int TryCull(Matrix viewproj)
        {
            int t1, t2, t3, t4;
            t1 = t2 = t3 = t4 = 0;

            int i;
            for (i = 0; i < 8; i++)
                m_projCorners[i] = Vector4.Transform(m_corners[i], viewproj);

            // Check each of the transformed corners of our bounding box
            // to see if it was transformed completely outside of 
            // the viewing frustrum, partially out or completely within.
            // w now represents the relative viewing frustrums extents
            // so, valid coords within viewing frustrum are
            //      0 <= z <= w && -w <= x <= w && -w <= y <= w
            //   or z >= 0 && z < w && x >= -w && x <= w && y >= -w && y <= w

            for (i = 0; i < 8; i++)
                if (m_projCorners[i].Z < 0.0f)
                    t1++;
            if (t1 >= 8)
                return 0; // completely behind Frustrum?

            for (i = 0; i < 8; i++)
                if (m_projCorners[i].X > m_projCorners[i].W)
                    t2++;
            if (t2 >= 8)
                return 0;

            for (i = 0; i < 8; i++)
                if (m_projCorners[i].X < -m_projCorners[i].W)
                    t3++;
            if (t3 >= 8)
                return 0;

            for (i = 0; i < 8; i++)
                if (m_projCorners[i].Z > m_projCorners[i].W)
                    t4++;
            if (t4 >= 8)
                return 0;

            if ((t1 + t2 + t3 + t4) == 0)
                return 1;

            return -1; // partially
        }

        //-------------------------------------------
        //  Draw this node if at least partially visible
        //-------------------------------------------

        public void Draw(GraphicsDevice gd, Matrix viewproj, bool bCheckCull)
        {
            nodeDrawn = false; // used by DrawModels;

            int cull = 1; // if cull == 0 then completely out of frustrum, 1 = in, -1 = partially
            //bCheckCull = false;
            if (bCheckCull)
            {
                cull = TryCull(viewproj);
                if (cull == 0) // completely out?
                    return;
            }

            nodeDrawn = true;

            if (m_vertexBuffer != null)
            {
                gd.Vertices[0].SetSource(m_vertexBuffer, 0, VertexPositionNormalTexture.SizeInBytes);
                gd.Indices = m_indexBuffer;

                gd.DrawIndexedPrimitives(
                    PrimitiveType.TriangleList,
                    0,  // vertex buffer offset to add to each element of the index buffer
                    0,  // minimum vertex index
                    m_numVerts, // number of vertices
                    0,  // first index element to read
                    m_numTris   // number of primitives to draw
                );
            }
            for (int i = 0; i < 4; i++)
            {
                if (child[i] != null)
                    child[i].Draw(gd, viewproj, cull < 0);
            }
        }


        //-------------------------------------------
        //-------------------------------------------

        public void DrawModels(Matrix view, Matrix proj)
        {
            // if we did _not_ draw the terrain node
            // then we don't need to draw any models 
            // that sit on it. (TODO: this is true except
            // for a special case which I'll handle later).
            if (!nodeDrawn)
                return;

            for (int i = 0; i < 4; i++)
            {
                if (child[i] != null)
                    child[i].DrawModels(view, proj);
            }

            if (models == null)
                return;

            if (models.Count < 1)
                return;

            foreach (QuadtreeModelInfo minfo in models)
            {
                // let's copy the varibles out of the QuadtreeModelInfo
                // structure just for code clatiry
                Model m = minfo.model;
                Vector3 modelPosition = minfo.position;
                float modelScale = minfo.scale;
                Vector3 modelRotation = minfo.rotation;

                Matrix[] transforms = new Matrix[m.Bones.Count];
                m.CopyAbsoluteBoneTransformsTo(transforms);

                //Draw the model, a model can have multiple meshes, so loop
                foreach (ModelMesh mesh in m.Meshes)
                {
                    //This is where the mesh orientation is set, as well as our camera and projection
                    foreach (BasicEffect effect in mesh.Effects)
                    {
                        //effect.EnableDefaultLighting();
                        effect.World = transforms[mesh.ParentBone.Index] * Matrix.CreateScale(modelScale)
                            * Matrix.CreateRotationX(modelRotation.X)
                            * Matrix.CreateRotationZ(modelRotation.Z)
                            * Matrix.CreateRotationY(modelRotation.Y)
                            * Matrix.CreateTranslation(modelPosition);
                        effect.View = view;
                        effect.Projection = proj;
                    }
                    //Draw the mesh, will use the effects set above.
                    mesh.Draw();
                }
            }
        }


        internal bool AddModel(QuadtreeModelInfo modelInfo)
        {
            if (models == null)
                return false;

            if (modelInfo.position.X >= m_startX && modelInfo.position.X < m_endX)
            {
                if (modelInfo.position.Z >= m_startY && modelInfo.position.Z < m_endY)
                {
                    // it belongs to this instance or a child

                    if (child != null)
                    {
                        for (int i = 0; i < 4; i++)
                        {
                            if (child[i] != null)
                            {
                                if (child[i].AddModel(modelInfo))
                                    return true;
                            }
                        }
                    }
                    // up to us to store it
                    if (modelInfo.position.Y == 0)
                        modelInfo.position.Y = GetHeightAt(modelInfo.position.X, modelInfo.position.Z);
                    modelInfo.node = this;
                    models.Add(modelInfo);
                    return true;
                }
            }
            return false;
        }

        internal bool RemoveModel(QuadtreeModelInfo modelInfo)
        {
            if (models.Contains(modelInfo))
            {
                models.Remove(modelInfo);
                return true;
            }
            return false;
        }

        //-------------------------------------------
        // QuadtreeGameComponent maintenance
        //-------------------------------------------

        public void DrawComponents(GameTime gameTime, Matrix view, Matrix proj)
        {
            // if we did _not_ draw the terrain node
            // then we don't need to draw any models 
            // that sit on it. (TODO: this is true except
            // for a special case which I'll handle later).
            if (!nodeDrawn)
                return;

            if (gameComponents != null)
            {
                foreach (QuadtreeGameComponent component in gameComponents)
                {
                    component.Draw(gameTime, view, proj);
                }
            }

            if (child != null)
            {
                for (int i = 0; i < 4; i++)
                {
                    if (child[i] != null)
                        child[i].DrawComponents(gameTime, view, proj);
                }
            }
        }

        internal bool AddComponent(QuadtreeGameComponent component)
        {
            if (gameComponents == null)
                return false;

            if (!IsInThisNode(component.Position))
                return false;

            if (child != null)
            {
                for (int i = 0; i < 4; i++)
                {
                    if (child[i] != null)
                    {
                        if (child[i].AddComponent(component))
                            return true;
                    }
                }
            }
            // up to us to store it
            if (component._position.Y == 0)
                component._position.Y = GetHeightAt(component.Position.X, component.Position.Z);
            component.qNode = this;
            gameComponents.Add(component);
            return true;
        }

        internal bool RemoveComponent(QuadtreeGameComponent component)
        {
            if (gameComponents.Contains(component))
            {
                gameComponents.Remove(component);
                component.qNode = null;
                return true;
            }
            return false;
        }


        //-------------------------------------------
        //-------------------------------------------

        internal bool IsInThisNode(float x, float z)
        {
            if (x >= m_startX && x < m_endX)
            {
                if (z >= m_startY && z < m_endY)
                {
                    return true;
                }
            }
            return false;
        }

        internal bool IsInThisNode(Vector3 position)
        {
            return IsInThisNode(position.X, position.Z);
        }

        //-------------------------------------------
        //  Get the terrain height at location x, y
        //  returns OutOfRange if x,y is off terrain
        //-------------------------------------------

        private static float OutOfRange = -987654321.0f;

        public float GetHeightAt(float x, float y)
        {
            if (x < m_startX || x >= m_endX)
                return OutOfRange;
            if (y < m_startY || y >= m_endY)
                return OutOfRange;

            if (m_heightData == null)
            {
                for (int i = 0; i < 4; i++)
                {
                    float ret;
                    if (child[i] != null)
                    {
                        ret = child[i].GetHeightAt(x, y);
                        if (ret != OutOfRange)
                            return ret;
                    }
                }
                return OutOfRange;
            }

            // up to this instance....

            // find the cell

            float thisX = x - m_startX;
            float thisY = y - m_startY;
            int mapX = (int)(thisX / m_cellSize);
            int mapY = (int)(thisY / m_cellSize);
            if (mapX < 0 || mapX >= m_width)
                throw new Exception("QuadtreeNode:GetHeightAt(x,y) x out of range.");
            if (mapY < 0 || mapY >= m_height)
                throw new Exception("QuadtreeNode:GetHeightAt(x,y) y out of range.");

            // compute distance into cell

            float deltaX = (thisX % m_cellSize) / m_cellSize;
            float deltaY = (thisY % m_cellSize) / m_cellSize;

            // find which tri in the cell to use

            float hx1, hx2;
            float hy1, hy2;
            if (deltaY < deltaX) // in the upper left tri?
            {
                hx1 = m_heightData[mapY, mapX];
                hx2 = m_heightData[mapY, mapX + 1];
                hy1 = m_heightData[mapY, mapX];
                hy2 = m_heightData[mapY + 1, mapX];
            }
            else
            {
                hx1 = m_heightData[mapY + 1, mapX];
                hx2 = m_heightData[mapY + 1, mapX + 1];
                hy1 = m_heightData[mapY, mapX + 1];
                hy2 = m_heightData[mapY + 1, mapX + 1];
            }

            // find height at that spot within the cell

            float height = ((hx1 + ((hx2 - hx1) * deltaX)) + (hy1 + ((hy2 - hy1) * deltaY))) / 2.0f;
            return height;
        }

        public Collection<NodeDrawn> GetNodesDrawn(int level)
        {
            if (_nodesDrawn == null)
                _nodesDrawn = new Collection<NodeDrawn>();

            if (level == 0) // if we are the root of this request
                _nodesDrawn.Clear();

            if (nodeDrawn)
            {
                if (level == 0 || m_vertexBuffer != null)
                    _nodesDrawn.Add(new NodeDrawn(level, m_startX, m_startY, m_endX, m_endY));

                if (child != null)
                {
                    for (int i = 0; i < 4; i++)
                    {
                        if (child[i] != null)
                            child[i].GetNodesDrawn(level + 1);
                    }
                }
            }
            return _nodesDrawn;
        }

        //-------------------------------------------
        //  Instance variables
        //-------------------------------------------

        protected float m_startX;
        protected float m_startY;
        protected float m_endX;
        protected float m_endY;
        protected float m_minHeight;
        protected float m_maxHeight;
        // Pre-calulate the corners or this node (used by TryCull)
        protected Vector3[] m_corners;
        // projected corners will be calculated in TryCull each frame
        protected Vector4[] m_projCorners;


        protected int m_width;
        protected int m_height;
        protected float m_cellSize;
        protected float[,] m_heightData;

        protected bool nodeDrawn;
        protected QuadTreeNode[] child;

        protected int m_numVerts;
        protected VertexBuffer m_vertexBuffer;
        protected int m_numTris;
        protected IndexBuffer m_indexBuffer;

        protected QuadTreeNode m_parent;
        private Collection<QuadtreeModelInfo> models;
        private Collection<QuadtreeGameComponent> gameComponents;

        static internal Collection<NodeDrawn> _nodesDrawn;
    }

    public class NodeDrawn
    {
        internal NodeDrawn(int lev, float lX, float tZ, float rX, float bZ)
        {
            level = lev;
            upperLeft.X = lX;
            upperLeft.Y = tZ;
            lowerRight.X = rX;
            lowerRight.Y = bZ;
        }
        public int level;
        public Vector2 upperLeft;
        public Vector2 lowerRight;
    }


    //============================================================
    //  QuadTree
    //============================================================

    public class Quadtree : DrawableGameComponent
    {
        private bool m_valid;
        private QuadTreeNode m_root;
        private int m_sectorsize;
        private float totalWidth;
        private float totalHeight;
        private BasicEffect m_basicEffect;
        private VertexDeclaration m_vertexDecl;
        private Matrix m_view;
        private Matrix m_projection;
        private Matrix m_viewproj;
        private Collection<QuadtreeGameComponent> gameComponents;

        /// <summary>
        /// Constructs a Quadtree object
        /// </summary>
        public Quadtree(Game game)
            : base(game)
        {
            m_valid = false;
            m_root = null;
            gameComponents = new Collection<QuadtreeGameComponent>();
        }

        //------------------------------------------------
        // Properties
        //------------------------------------------------

        /// <summary>
        /// Returns true if this QuadTree contains valid data for rendering
        /// </summary>
        public bool Valid
        {
            get { return m_valid; }
        }

        /// <summary>
        /// Set the View matrix before calling Draw()
        /// </summary>
        public Matrix View
        {
            set { m_view = value; }
        }


        /// <summary>
        /// Set the Projection matrix before calling Draw()
        /// </summary>
        public Matrix Projection
        {
            set { m_projection = value; }
        }

        /// <summary>
        /// Gets or Sets the Large Texture to use on the entire terrain once
        /// </summary>
        public Texture2D Texture
        {
            get { return m_basicEffect.Texture; }
            set
            {
                m_basicEffect.Texture = value;
                m_basicEffect.TextureEnabled = (m_basicEffect.Texture != null);
            }
        }

        /// <summary>
        /// Gets or Sets the ambient light for the terrain
        /// </summary>
        public Vector3 AmbientLight
        {
            get { return m_basicEffect.AmbientLightColor; }
            set { m_basicEffect.AmbientLightColor = value; }
        }

        /// <summary>
        /// Gets or Sets the value that determines whether to use fog on the terrain
        /// </summary>
        public bool FogEnabled
        {
            get { return m_basicEffect.FogEnabled; }
            set { m_basicEffect.FogEnabled = value; }
        }

        /// <summary>
        /// Gets or Sets the color for the Fog
        /// </summary>
        public Vector3 FogColor
        {
            get { return m_basicEffect.FogColor; }
            set { m_basicEffect.FogColor = value; }
        }

        /// <summary>
        /// Gets or Sets the distance from the camera to start the fog.
        /// </summary>
        public float FogStart
        {
            get { return m_basicEffect.FogStart; }
            set { m_basicEffect.FogStart = value; }
        }

        /// <summary>
        /// Gets or Sets the distance from the camera for the fog to completely obscure the terrain.
        /// </summary>
        public float FogEnd
        {
            get { return m_basicEffect.FogEnd; }
            set { m_basicEffect.FogEnd = value; }
        }

        /// <summary>
        /// Gets the BasicEffect object that this quadtree terrain uses
        /// </summary>
        public BasicEffect Effect
        {
            get { return m_basicEffect; }
        }

        public float Width
        {
            get { return totalWidth; }
        }
        public float Height
        {
            get { return totalHeight; }
        }

        //-------------------------------------------------
        // DrawableGameComponent overrides
        //-------------------------------------------------

        /// <summary>
        /// Initializes this Quadtree and any QuadtreeGameComponents
        /// that were added to it up till now.
        /// </summary>
        public override void Initialize()
        {
            base.Initialize(); // base must initialize first so that this.graphicsDevice is valid

            m_vertexDecl = new VertexDeclaration(
                this.GraphicsDevice, VertexPositionNormalTexture.VertexElements);

            CreateEffect();

            foreach (QuadtreeGameComponent component in gameComponents)
                component.Initialize();
        }

        /// <summary>
        /// Calls Update on QuadtreeGameComponents that were added to 
        /// this Quadtree up till now.
        /// </summary>
        public override void Update(GameTime gameTime)
        {
            base.Update(gameTime);

            foreach (QuadtreeGameComponent component in gameComponents)
                component.Update(gameTime);
        }

        protected override void LoadGraphicsContent(bool loadAllContent)
        {
            base.LoadGraphicsContent(loadAllContent);

            foreach (QuadtreeGameComponent component in gameComponents)
                component.X_LoadGraphicsContent(loadAllContent);
        }

        protected override void UnloadGraphicsContent(bool unloadAllContent)
        {
            base.UnloadGraphicsContent(unloadAllContent);

            foreach (QuadtreeGameComponent component in gameComponents)
                component.X_UnloadGraphicsContent(unloadAllContent);
        }

        /// <summary>
        /// Draws the terrain contained in this QuadTree.
        /// Be sure to set the View and Projection matrices
        /// as well as other attributes before this Draw method is called.
        /// </summary>
        /// <param name="gameTime">Time since last Draw</param>
        public override void Draw(GameTime gameTime)
        {
            if (m_basicEffect == null)
                CreateEffect();

            if (m_valid && m_root != null)
            {
                m_viewproj = m_view * m_projection;

                m_basicEffect.Projection = m_projection;
                m_basicEffect.View = m_view;
                m_basicEffect.World = Matrix.Identity;

                m_basicEffect.Begin();
                foreach (EffectPass pass in m_basicEffect.CurrentTechnique.Passes)
                {
                    pass.Begin();

                    this.GraphicsDevice.VertexDeclaration = m_vertexDecl;
                    this.GraphicsDevice.RenderState.CullMode = CullMode.CullCounterClockwiseFace;

                    m_root.Draw(this.GraphicsDevice, m_viewproj, true);

                    pass.End();
                }

                m_basicEffect.End();

                // Draw any models and components in the tree

                m_root.DrawModels(m_view, m_projection);

                m_root.DrawComponents(gameTime, m_view, m_projection);
            }
        }

        /// <summary>
        /// Creates the QuadTree nodes and initializes them for rendering.
        /// This method must be called after content is loaded but before Draw().
        /// The texture heightmap is no longer needed by QuadTree upon return.
        /// </summary>
        /// <param name="heightMap">An uncompressed Texture2D HeightMap to use for height data.</param>
        /// <param name="cellSize">Width/Height of a cell in the terrain</param>
        /// <param name="sectorsize">Number of cells in x and z that will be rendered or culled as a unit</param>
        public bool Create(Texture2D heightMap, float cellSize, int sectorSize)
        {
            SurfaceFormat fmt = heightMap.Format;
            Int32[] data = new Int32[heightMap.Width * heightMap.Height];
            heightMap.GetData<Int32>(data);

            float[,] floatHeightData = ConvertARGBtoFloatHeightData(heightMap.Width, heightMap.Height, 2.5f, data);
            data = null; // done with it..

            return Create(cellSize, sectorSize, floatHeightData);
        }

        /// <summary>
        /// Creates the QuadTree nodes and initializes them for rendering.
        /// This method must be called after content is loaded but before Draw().
        /// </summary>
        /// <param name="cellSize">Width/Height of a cell in the terrain</param>
        /// <param name="sectorsize">Number of cells in x and z that will be rendered or culled as a unit</param>
        /// <param name="heightData">The HeightData to use.</param>
        public bool Create(float cellSize, int sectorSize, float[,] heightData)
        {
            int width = heightData.GetLength(1);
            int height = heightData.GetLength(0);

            totalWidth = cellSize * width;
            totalHeight = cellSize * height;

            m_sectorsize = sectorSize;

            if (height > heightData.GetLength(0))
                m_valid = false;
            if (width > heightData.GetLength(1))
                m_valid = false;


            Vector3[,] normals = CreateNormals(cellSize, heightData);

            m_root = new QuadTreeNode(null);
            m_valid = m_root.Buildout(this.GraphicsDevice, cellSize, sectorSize, 0, 0, width, height, heightData, normals);
            if (!m_valid)
                m_root = null;

            normals = null; // don't need them anymore here

            // if we have QuadtreeGameComponents added to the quadtree already
            // then distribute them to the new nodes

            if (m_valid && m_root != null)
            {
                foreach (QuadtreeGameComponent component in gameComponents)
                    m_root.AddComponent(component);
            }

            return m_valid;
        }

        /// <summary>
        /// Returns the interpolated height on the heightmap at location x,z
        /// will return a negative number (<0.0f) if off the terrain.
        /// </summary>
        /// <param name="x">X location within terrain</param>
        /// <param name="z">Z location within terrain</param>
        public float GetHeightAt(float x, float z)
        {
            return m_root.GetHeightAt(x, z);
        }

        /// <summary>
        /// Returns a collection of NodeDrawn objects that
        /// represent the position of all quadtree nodes
        /// that were included for drawing the last frame.
        /// NOTE: this includes parent nodes.
        /// Returns null if Quadtree not yet created.
        /// </summary>
        public Collection<NodeDrawn> GetNodesDrawn()
        {
            if (m_valid && m_root != null)
                return m_root.GetNodesDrawn(0);
            return null;
        }

        /// <summary>
        /// Add a model to the terrain.  
        /// Returns null if not on terrain or Quadtree not created.
        /// </summary>
        /// <param name="model">Model to add</param>
        /// <param name="position">where to put the model</param>
        /// <param name="scale">scaling if needed, else 1.0f</param>
        /// <param name="rotationY">orientation, rotation about the Y/Up axis</param>
        public QuadtreeModelInfo AddModel(Model model, Vector3 position, float scale, Vector3 rotation)
        {
            if (m_valid && m_root != null)
            {
                QuadtreeModelInfo modelInfo = new QuadtreeModelInfo(model, position, scale, rotation);
                if (m_root.AddModel(modelInfo)) //position, scale, rotationY, model);
                    return modelInfo;
            }
            return null;
        }

        /// <summary>
        /// Lets the Quadtree know of the new position of a model
        /// </summary>
        /// <param name="modelInfo">ModelInfo object returned from AddModel</param>
        /// <param name="position">where to put the model</param>
        public void UpdateModelPosition(QuadtreeModelInfo modelInfo, Vector3 position)
        {
            if (m_valid && m_root != null)
            {
                if (modelInfo != null)
                {
                    if (modelInfo.node != null)
                        modelInfo.node.RemoveModel(modelInfo);
                    modelInfo.position = position;
                    m_root.AddModel(modelInfo);
                }
                return;
            }
            return;
        }

        /// <summary>
        /// Removes a model and it's associated data from the terrain
        /// Returns the Model that was contained in the QuadtreeModelInfo,
        /// or null if modelInfo is null or contains a null Model reference.
        /// </summary>
        /// <param name="modelInfo">A QuadtreeModelInfo object returned from AddModel()</param>
        public Model RemoveModel(QuadtreeModelInfo modelInfo)
        {
            if (modelInfo != null)
            {
                if (modelInfo.node != null)
                    modelInfo.node.RemoveModel(modelInfo);
                return modelInfo.model;
            }
            return null;
        }

        /// <summary>
        /// Adds a QuadtreeGameComponent to the Quadtree
        /// </summary>
        /// <param name="component">QuadtreeGameComponent to add</param>
        /// <param name="position">where to put the model</param>
        public bool AddComponent(QuadtreeGameComponent component)
        {
            if (!gameComponents.Contains(component))
                gameComponents.Add(component);

            if (component.qNode != null && component._quadtree == this)
                component.qNode.RemoveComponent(component);
            component.qNode = null;

            component._quadtree = this;

            if (m_valid && m_root != null)
                m_root.AddComponent(component);

            return true;
        }

        /// <summary>
        /// Removes a QuadtreeGameComponent derrived object from the Quadtree
        /// </summary>
        /// <param name="component">A QuadtreeGameComponent object previously added to the Quadtree</param>
        public void RemoveComponent(QuadtreeGameComponent component)
        {
            if (component != null)
            {
                if (component._quadtree != this)
                    return; // wrong quadtree or never added

                if (component.qNode != null)
                    component.qNode.RemoveComponent(component);
                component.qNode = null;

                if (gameComponents.Contains(component))
                    gameComponents.Remove(component);
                component._quadtree = null;
            }
        }

        //-----------------------------------------------
        //  Create Normals
        //-----------------------------------------------

        private Vector3[,] CreateNormals(float cellSize, float[,] heightData)
        {
            int height = heightData.GetLength(0);
            int width = heightData.GetLength(1);

            Vector3[,] normals = new Vector3[height, width];
            if (normals == null)
                throw new Exception("QuadTree:CreateNormals() Out of memory for Normals");


            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    if (x == 0 || y == 0 || x == (width - 1) || y == (height - 1))
                    {
                        // Border vertices (lazy way to deal with these special cases)
                        normals[y, x] = Vector3.Up;
                    }
                    else
                    {
                        Vector3 pos = new Vector3(cellSize * x, heightData[y, x], cellSize * y);
                        Vector3 pos2;
                        Vector3 pos3;
                        Vector3 norm1;
                        Vector3 norm2;
                        Vector3 norm3;
                        Vector3 norm4;
                        Vector3 norm5;
                        Vector3 norm6;

                        pos2 = new Vector3(cellSize * (x), heightData[y - 1, x], cellSize * (y - 1));
                        pos3 = new Vector3(cellSize * (x - 1), heightData[y, x - 1], cellSize * (y));
                        pos2 -= pos;
                        pos3 -= pos;
                        pos2.Normalize();
                        pos3.Normalize();
                        norm1 = Vector3.Cross(pos2, pos3);

                        pos2 = new Vector3(cellSize * (x - 1), heightData[y, x - 1], cellSize * (y));
                        pos3 = new Vector3(cellSize * (x - 1), heightData[y + 1, x - 1], cellSize * (y + 1));
                        pos2 -= pos;
                        pos3 -= pos;
                        pos2.Normalize();
                        pos3.Normalize();
                        norm2 = Vector3.Cross(pos2, pos3);

                        pos2 = new Vector3(cellSize * (x - 1), heightData[y + 1, x - 1], cellSize * (y + 1));
                        pos3 = new Vector3(cellSize * (x), heightData[y + 1, x], cellSize * (y + 1));
                        pos2 -= pos;
                        pos3 -= pos;
                        pos2.Normalize();
                        pos3.Normalize();
                        norm3 = Vector3.Cross(pos2, pos3);

                        pos2 = new Vector3(cellSize * (x), heightData[y + 1, x], cellSize * (y + 1));
                        pos3 = new Vector3(cellSize * (x + 1), heightData[y, x + 1], cellSize * (y));
                        pos2 -= pos;
                        pos3 -= pos;
                        pos2.Normalize();
                        pos3.Normalize();
                        norm4 = Vector3.Cross(pos2, pos3);

                        pos2 = new Vector3(cellSize * (x + 1), heightData[y, x + 1], cellSize * (y));
                        pos3 = new Vector3(cellSize * (x + 1), heightData[y - 1, x + 1], cellSize * (y - 1));
                        pos2 -= pos;
                        pos3 -= pos;
                        pos2.Normalize();
                        pos3.Normalize();
                        norm5 = Vector3.Cross(pos2, pos3);

                        pos2 = new Vector3(cellSize * (x + 1), heightData[y - 1, x + 1], cellSize * (y - 1));
                        pos3 = new Vector3(cellSize * (x), heightData[y - 1, x], cellSize * (y - 1));
                        pos2 -= pos;
                        pos3 -= pos;
                        pos2.Normalize();
                        pos3.Normalize();
                        norm6 = Vector3.Cross(pos2, pos3);

                        Vector3 norm = (norm1 + norm2 + norm3 + norm4 + norm5 + norm6) / 6.0f;

                        normals[y, x] = Vector3.Normalize(norm);
                    }
                }
            }
            return normals;
        }

        //-----------------------------------------------
        // Convert a textures data to an array of floats
        //-----------------------------------------------

        protected float[,] ConvertARGBtoFloatHeightData(int width, int height, float yScale, Int32[] data)
        {
            int size = data.Length;
            if (size != width * height)
                return null;

            float[,] ret = new float[height, width];

            int r = 0;
            int c = 0;
            for (int i = 0; i < size; i++)
            {
                ret[r, c++] = (float)(data[i] & 0x000000FF) * yScale;
                c %= width;
                if (c == 0)
                    r++;
            }
            return ret;
        }
        //-----------------------------------------------
        //  CreateEffect for the terrain
        //-----------------------------------------------

        protected void CreateEffect()
        {
            m_basicEffect = new BasicEffect(this.GraphicsDevice, null);
            m_basicEffect.Alpha = 1.0f;
            m_basicEffect.DiffuseColor = new Vector3(1.0f, 1.0f, 1.0f); //(1.0f, 1.0f, 0.0f);
            m_basicEffect.SpecularColor = new Vector3(0.25f, 0.25f, 0.25f);
            m_basicEffect.SpecularPower = 5.0f;

            m_basicEffect.AmbientLightColor = new Vector3(0.4f, 0.4f, 0.5f);

            m_basicEffect.DirectionalLight0.Enabled = true;
            m_basicEffect.DirectionalLight0.DiffuseColor = Vector3.One;
            m_basicEffect.DirectionalLight0.Direction = Vector3.Normalize(new Vector3(1.5f, -0.15f, -0.5f));
            m_basicEffect.DirectionalLight0.SpecularColor = Vector3.One;

            m_basicEffect.DirectionalLight1.Enabled = false; // true;
            m_basicEffect.DirectionalLight1.DiffuseColor = new Vector3(0.5f, 0.5f, 0.5f);
            m_basicEffect.DirectionalLight1.Direction = Vector3.Normalize(new Vector3(-1.0f, -1.0f, 1.0f));
            m_basicEffect.DirectionalLight1.SpecularColor = new Vector3(0.5f, 0.5f, 0.5f);

            m_basicEffect.LightingEnabled = true;

            m_basicEffect.FogColor = Color.CornflowerBlue.ToVector3(); // new Vector3(0.75f, 0.75f, 0.75f);
            m_basicEffect.FogStart = 3000.0f;
            m_basicEffect.FogEnd = 4000.0f - 2.0f;
            m_basicEffect.FogEnabled = true;
        }
    }
}
